﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
#include"Queue.h"
//前序遍历
void qian(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->arr);
	qian(root->zuo);
	qian(root->you);
}
//中序遍历
void zho(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	zho(root->zuo);
	printf("%d ", root->arr);
	zho(root->you);
}
//后序遍历
void ho(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	ho(root->zuo);
	ho(root->you);
	printf("%d ", root->arr);
}

//二叉树节点个数
int BinaryTreeSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->zuo) + BinaryTreeSize(root->you);
}

// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (BinaryTreeLeafSize(root->zuo) == NULL && BinaryTreeLeafSize(root->you) == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->zuo) + BinaryTreeLeafSize(root->you);
}
// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BT* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->zuo, k - 1) + BinaryTreeLevelKSize(root->you, k - 1);
}


//⼆叉树的深度/⾼度
int BinaryTreeDepth(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int zuo = BinaryTreeDepth(root->zuo);
	int you = BinaryTreeDepth(root->you);
	return zuo > you ? zuo + 1 : you + 1;
}


// ⼆叉树查找值为x的结点 
BT* BinaryTreeFind(BT* root, ercsdata x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->arr == x)
	{
		return root;
	}
	BT* zuo = BinaryTreeFind(root->zuo, x);
	if (zuo != NULL)
	{
		return zuo;
	}
	BT* you = BinaryTreeFind(root->you, x);
	if (you != NULL)
	{
		return you;
	}
}

//二叉树销毁
void ercs_xiaoh(BT** root)
{
	if (*root == NULL)
	{
		return;
	}
	ercs_xiaoh(&(*root)->zuo);
	ercs_xiaoh(&(*root)->you);
	free(*root);
	*root = NULL;
}
//层序遍历
//借助数据结构--队列
void LevelOrder(BT* root)
{
	Queue add;
	//初始化
	Queuecsh(&add);
	//入数据
	Queue_ruwei(&add, root);

	while (!buer(&add))
	{
		//取队头-打印
		BT* tab = qto(&add);
		printf("%d ", tab->arr);
		//出队
		Queue_chu(&add);
		//判断是不是空， 队头节点的左右孩子入，队列
		if (tab->zuo)
		{
			Queue_ruwei(&add, tab->zuo);
		}
		if (tab->you)
		{
			Queue_ruwei(&add, tab->you);
		}
	}

	//队列销毁
	Queuexiaoh(&add);
}

bool pdercs(BT* root)
{
	Queue add;
	//队列初始化
	Queuecsh(&add);
	//入队列
	Queue_ruwei(&add, root);
	while (!buer(&add))
	{
		//取队头数据
		BT* tab =  qto(&add);
		//出队
		Queue_chu(&add);
		if (tab == NULL)
		{
			//等于空结束循环
			break;
		}//不为空让左右子树入队列

		//左子树_入队列
		Queue_ruwei(&add, tab->zuo);
		//右子树_入队列
		Queue_ruwei(&add, tab->you);
	}
	//循环判断队列，有一个数值不是完全二叉树，都是NULL就是完全二叉树
	while (!buer(&add))
	{
		//取队头
		BT* app = qto(&add);
		//出队
		Queue_chu(&add);
		//判断如果还有非空节点，返回false
		if (app != NULL)
		{
			Queuexiaoh(&add);
			return false;
		}
	}//循环完，说明队列里都是NULL,是完全二叉树，返回true

	//队列销毁
	Queuexiaoh(&add);
	return true;
}
//
//// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
//BT* BinaryTreeCreate(BTdata* a, int n, int* pi)
//{
//	if (a == NULL)
//	{
//		return;
//	}
//
//}

////前序遍历
//void qian(BT* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	printf("%d ", root->arr);
//	qian(root->zuo);
//	qian(root->you);
//}